Little Bird

Memory limit: 128 MB

In the Byteotian Line Forest there are trees in a row. On top of the first one, there is a little bird who would like to fly over to the top of the last tree. Being in fact very little, the bird might lack the strength to fly there without any stop. If the bird is sitting on top of the tree no. , then in a single flight leg it can fly to any of the trees no. , and then has to rest afterward.

Moreover, flying up is far harder to flying down. A flight leg is tiresome if it ends in a tree at least as high as the one where is started. Otherwise the flight leg is not tiresome.

The goal is to select the trees on which the little bird will land so that the overall flight is least tiresome, i.e., it has the minimum number of tiresome legs. We note that birds are social creatures, and our bird has a few bird-friends who would also like to get from the first tree to the last one. The stamina of all the birds varies, so the bird's friends may have different values of the parameter . Help all the birds, little and big!

Input

There is a single integer () in the first line of the standard input: the number of trees in the Byteotian Line Forest. The second line of input holds integers () separated by single spaces: is the height of the -th tree.

The third line of the input holds a single integer (): the number of birds whose flights need to be planned. The following lines describe these birds: in the -th of these lines, there is an integer () specifying the -th bird's stamina. In other words, the maximum number of trees that the -th bird can pass before it has to rest is .

In test worth at least of total score, the condition holds. In a subset of those worth of total score, it even holds that .

Output

Your program should print exactly lines to the standard output. In the -th line, it should specify the minimum number of tiresome flight legs of the -th bird.

Example

For the input data:

9
4 6 3 6 3 7 2 6 5
2
2
5

the correct result is:

2
1

Explanation: The first bird may stop at the trees no. 1, 3, 5, 7, 8, 9. Its tiresome flight legs will be the one from the -rd tree to the -th one and from the -th to the -th.

Sample grading tests:

• 1ocen: , , , all trees of same height, the answer is (a stopover at the -th tree suffices);
• 2ocen: , , , , tree heights alternate between and - it is optimal for both birds to stop after every trees, for tiresome legs for each bird;
• 3ocen: , , , the sequence of heights is: , the answer is ;
• 4ocen: , , , , the remaining ones satisfy .

Task author: Jacek Tomasiewicz.